package com.zhugang.week09;

/**
 * @program algorithms
 * @description: numIslands
 * @author: chanzhugang
 * @create: 2022/08/22 19:02
 */
public class NumIslands {

    /**
     * 200 岛屿数量
     * 图的连通分量
     *
     * @param grid
     * @return
     */
    private boolean[][] visited;
    private int h;
    private int w;

    public int numIslands(char[][] grid) {
        // 1 陆地 0 水
        // 抽象成图的DFS
        h = grid.length;
        w = grid[0].length;
        visited = new boolean[h][w];
        int result = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (visited[i][j] != true && grid[i][j] == '1') {
                    result++;
                    dfs(grid, i, j);
                }
            }
        }
        return result;
    }

    private void dfs(char[][] grid, int i, int j) {
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        visited[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int newi = i + directions[k][0];
            int newj = j + directions[k][1];
            if (newi >= 0 && newi < h && newj >= 0 && newj < w && visited[newi][newj] == false && grid[newi][newj] == '1') {
                // 多个岛屿连着，数量不加
                dfs(grid, newi, newj);
            }
        }
    }

}